package wheel;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * The Probability class is responsible for determining the most probable
 * letter choice given the words (and guesses) in a puzzle.
 *  
 * @author Steve Gennaoui, Jack Myers
 *
 */
public class Probability {
	protected static enum LetterType{CONSONANT, VOWEL};
	private static final int NUM_LETTERS_IN_ALPHABET = 26;
	// All consonants and vowels ordered by frequency found in English (as a string) 
	private static String consonantsAndVowels = Computer.consonantsInOrder + Computer.vowelsInOrder;
	// All consonants and vowels ordered by frequency found in English (as an array)
	private static final char[] letters = consonantsAndVowels.toCharArray(); 

	/**
	 * Finds the most probable consonant for a given set of words and the probability of that consonant.
	 * @param wordsInPuzzle - The Words found in the puzzle
	 * @return The most probable consonant and its probability
	 */
	public static HashMap<Character, Double> findMostProbableConsonantForPuzzle(ArrayList<Word> wordsInPuzzle) {
		// Find most probable character and specify consonant
		return findMostProbableCharacterForPuzzle(wordsInPuzzle, LetterType.CONSONANT);
	}

	/**
	 * Finds the most probable vowel for a given set of words and the probability of that vowel.
	 * @param wordsInPuzzle - The Words found in the puzzle
	 * @return The most probable vowel and its probability
	 */
	public static HashMap<Character, Double> findMostProbableVowelForPuzzle(ArrayList<Word> wordsInPuzzle) {
		// Find most probable character and specify consonant
		return findMostProbableCharacterForPuzzle(wordsInPuzzle, LetterType.VOWEL);
	}

	/**
	 * Finds the most probable character for the given set of Words. Will only return the most
	 * probable consonant or vowel depending on the LetterType parameter.
	 * @param wordsInPuzzle - The Words in the puzzle
	 * @param typeWanted - Enumerated type, either Consonant or Vowel.
	 * @return @return The most probable vowel and its probability
	 */
	private static HashMap<Character, Double> findMostProbableCharacterForPuzzle(
			ArrayList<Word> wordsInPuzzle, LetterType typeWanted) {

		// This ArrayList will hold the array of probabilities of each letter appearing in a
		// word, based on the guesses available for that word. One double[] per word in wordsInPuzzle
		ArrayList<double[]> perWordLetterProbabilities = new ArrayList<double[]>();
		for (Word word: wordsInPuzzle) {
			// Add the array of probabilities of each letter appearing in a word based on the guesses
			// available for that word, to the arraylist of probabilities.
			perWordLetterProbabilities.add(calculateProbabilitiesOfLettersPerGuessesForWord(word));
		}

		// Will hold the overall probability of each letter appearing anywhere in the puzzle
		double[] probabilityOfLettersAppearingInPuzzle = new double[NUM_LETTERS_IN_ALPHABET];
		// Calculate overall puzzle probability of that letter appearing.
		// We consider the probability of each letter appearing in a Word to be independent of
		// its probability of appearing in another word.
		// For each letter
		for (int i=0; i < NUM_LETTERS_IN_ALPHABET; i++) {
			// For each word
			for (int j=0; j <= perWordLetterProbabilities.size()-1; j++) {
				// If this is the first probability to be calculated, union with 0 so overall probability
				// will be the same as the probability at this word/for this letter
				if (j==0)
					probabilityOfLettersAppearingInPuzzle[i] = union(0, perWordLetterProbabilities.get(j)[i]);
				// Otherwise, accumulate probability by using the union operation
				else
					probabilityOfLettersAppearingInPuzzle[i] =
						union(perWordLetterProbabilities.get(j)[i], probabilityOfLettersAppearingInPuzzle[i]);
			}
		}

		// maxValue will range from 0..1
		double maxValue = -1;
		// Create a list of all letters that have the same probability as the max probability.
		ArrayList<Character> mostProbableChoices = new ArrayList<Character>();
		// Find the most probable choices
		// For each letter
		for (int i=0; i < NUM_LETTERS_IN_ALPHABET; i++) {
			// If the character is the right type (consonant or vowel)
			if (charIsRightType(letters[i], typeWanted)) {
				// If the probability of this letter is the same as the probability
				// of the previous maximum probability
				if (maxValue == probabilityOfLettersAppearingInPuzzle[i]) {
					// Add this letter to the probable choices
					mostProbableChoices.add(letters[i]);
				}
				// If the probability of this letter is greater than the previous maximum
				if (probabilityOfLettersAppearingInPuzzle[i] > maxValue) {
					// Clear the list, update the max probability, add this letter
					maxValue = probabilityOfLettersAppearingInPuzzle[i];
					mostProbableChoices.clear();
					mostProbableChoices.add(letters[i]);
				}
			}
			// Else ignore this character. We will never want to return it.
		}

		// This is our return value. Instantiate it, but don't populate it yet. (will only ever be size one)
		HashMap<Character,Double> result = new HashMap<Character,Double>();
		// If there was only one "most probable" letter from the above calculation
		if (mostProbableChoices.size() == 1) {
			// populate the return value with this letter and its probability. 
			result.put(mostProbableChoices.get(0), maxValue);
		} else {
			// Otherwise populate it with the letter and probability from 
			// findMostUsefulLetter()
			result.put(findMostUsefulLetter(wordsInPuzzle, mostProbableChoices), maxValue);
		}
		// Return the result, which has been populated with exactly 1 letter.
		return result;
	}

	/**
	 * Finds the most useful letter for narrowing down guesses for the puzzle
	 * @param wordsInPuzzle The words in the puzzle
	 * @param lettersToCheck A list of letters that are considered to be the most likely character choices for these words
	 * @return The most useful letter
	 */
	protected static Character findMostUsefulLetter(ArrayList<Word> wordsInPuzzle, ArrayList<Character> lettersToCheck) {
		// Initialize this hashmap to have 0 indices spanned for each of the most likely characters
		HashMap<Character, Integer> uniqueIndexCountsPerCharacter = new HashMap<Character,Integer>();
		for (Character c: lettersToCheck) {
			uniqueIndexCountsPerCharacter.put(c, 0);
		}

		// For each word in the puzzle
    	for (Word word: wordsInPuzzle) {
    		// For each index in that word
    		for (int i = 0; i < word.getLength(); i++) {
    			// For each letter
    			for (Character c: lettersToCheck) {
    				// Check all guesses at that index for that letter
    				for (String guess: word.getGuesses().keySet()) {
    					guess = guess.toUpperCase(); // Always deal with guesses in upper case
    					// If this guess has the letter we're looking for..
    					if (guess.charAt(i) == c) {
    						// Increment the unique index count for this letter and check this guess/index combination
    						// again for the next letter.
    						uniqueIndexCountsPerCharacter.put(c, uniqueIndexCountsPerCharacter.get(c)+1);
    						break;
    					}
    				}
    			}
    		}
    	}

    	int maxNumberIndicesSpanned = 0;
    	// ArrayList of tied characters
    	ArrayList<Character> tiedForSpansMostIndices = new ArrayList<Character>();
    	// For each likely character
    	for (Character c: lettersToCheck) {
    		// If the indices spanned for this character is the same as the current maximum,
    		// add this character to the list of ties.
    		if (uniqueIndexCountsPerCharacter.get(c) == maxNumberIndicesSpanned) {
    			tiedForSpansMostIndices.add(c);
    		}
    		// If the indices spanned for this character is larger than the current maximum,
    		// update the maximum, clear the list of ties, and add this character to the list
    		if (uniqueIndexCountsPerCharacter.get(c) > maxNumberIndicesSpanned) {
    			maxNumberIndicesSpanned = uniqueIndexCountsPerCharacter.get(c);
    			tiedForSpansMostIndices.clear();
    			tiedForSpansMostIndices.add(c);
    		}
    	}

    	// If there are no ties, return the most useful character
    	if (tiedForSpansMostIndices.size() == 1) {
    		return tiedForSpansMostIndices.get(0);
    	}
    	
    	// Otherwise, we pick the character by the most potentially lucrative character
    	HashMap<Character, Integer> totalCountPerCharacter = new HashMap<Character,Integer>();
    	// Initialization
		for (Character c: tiedForSpansMostIndices) {
			totalCountPerCharacter.put(c, 0);
		}

		// For each word in the puzzle
    	for (Word word: wordsInPuzzle) {
    		// For each guess
    		for (String guess: word.getGuesses().keySet()) {
    			guess = guess.toUpperCase(); // Always deal with guesses in upper case
    			// For each index of the guesses
    			for (int i = 0; i < guess.length(); i++) {
    				// When we find one of the tied characters, increment its total count
    				for (Character c: tiedForSpansMostIndices) {
    					if (guess.charAt(i) == c) {
    						totalCountPerCharacter.put(c, totalCountPerCharacter.get(c)+1);
    					}
    				}
    			}
    		}
    	}

    	int maxCount = 0;
    	Character mostFrequent = null;
    	// For each character that was tied for most useful
    	for (Character c: tiedForSpansMostIndices) {
    		// If the count of Character c is greater than the current maximum,
    		// Update the maximum and the most frequent character
    		if (maxCount < totalCountPerCharacter.get(c)) {
    			maxCount = totalCountPerCharacter.get(c);
    			mostFrequent = c;
    		}
    	}
    	// Return the most useful character
    	return mostFrequent;
	}

	/**
	 * Determines whether a given character is of the specified type
	 * @param c Character to check
	 * @param t Type to check
	 * @return true if the character is of the type specified, false otherwise
	 */
	protected static boolean charIsRightType(char c, LetterType t) {
		if ((t == LetterType.CONSONANT && Game.isConsonant(c)) || 
			(t == LetterType.VOWEL && Game.isVowel(c)))
			return true;
		return false;
	}

	/**
	 * Given a word, find the probability of each letter appearing in that word based on the
	 * number of guesses the character appears in.
	 * @param wordFromPuzzle
	 * @return The probabilities of each letter appearing in the given word. Index 0 = P(A), Index 1 = P(B), etc
	 */
	protected static double[] calculateProbabilitiesOfLettersPerGuessesForWord(Word wordFromPuzzle) {
		// Get the guesses for this word
		HashMap<String,Guess> guesses = wordFromPuzzle.getGuesses();
		// Set the initial probabilities for each letter to be 0
		double[] letterProbabilities = new double[NUM_LETTERS_IN_ALPHABET];
		// Set the initial counts for each letter to be 0
		int[] letterCounts = new int[NUM_LETTERS_IN_ALPHABET];

		double weightedGuessCount = 0;
		// For each guess
		// guesses is a HashMap<String, Guess>
		// guess is the key to get the Guess object
		for (String guess: guesses.keySet()) {
			// Get the guess object
			Guess g = guesses.get(guess);
			// Get the weight of this guess (weights are based on sources)
			double guessWeight = g.getGuessWeight();
			// Add the guesses weight to the weightedGuessCount so we know the sum of weights
			weightedGuessCount += guessWeight;
			// Always deal with upper case
			guess = guess.toUpperCase();
			// For each letter in the alphabet
			for (int k=0; k < letters.length; k++) {
				// Get a letter
				char c = letters[k];
				// For each position in the guess
				for (int i=0; i < wordFromPuzzle.getLength(); i++) {
					// If this position is already solved, ignore it
					if (wordFromPuzzle.charAlreadySolved(i))
						continue;
					// Otherwise
					else {
						// If this position in this guess has this character, 
						// add the weight of the guess to the number of guesses this letter has appeared in
						if (guess.charAt(i) == c) {
							letterCounts[k] += guessWeight;
							break;	// We don't care how many times this letter appeared in this guess.
						}
					}
				}
			}
		}

		// As long as there was one guess
		if ( weightedGuessCount > 0.0) {
			// Determine the probability of each letter appearing in this word
			for (int i=0; i < letterProbabilities.length; i++) {
				letterProbabilities[i] = letterCounts[i] / weightedGuessCount;
			}
		}
		return letterProbabilities;
	}

	/**
	 * Calculates the union of two probabilities of disjoint events.
	 * @param probabilityOfEventA
	 * @param probabilityOfEventB
	 * @return
	 */
	protected static double union(double probabilityOfEventA, double probabilityOfEventB) {
		return 1 - ((1-probabilityOfEventA)*(1-probabilityOfEventB));
	}
	
	/**
	 * Calculates probability of two independent events occurring.
	 * @param probabilityOfEventA
	 * @param probabilityOfEventB
	 * @return 
	 */
	public static double intersection(double probabilityOfEventA, double probabilityOfEventB) {
		return probabilityOfEventA * probabilityOfEventB;
	}
}